package org.example.algorithm.graph;

public class NumIslandsUnionFindSolution {
    private int[] parent;
    private int[] rank;
    private int count = 0;

    public void initUnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i=0;i<size;i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if(rank[rootY] < rank[rootX]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
        }
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int row = grid.length;
        int column = grid[0].length;
        initUnionFind(row * column);
        for (int i=0;i<row;i++) {
            for (int j=0;j<column;j++) {
                if (grid[i][j] == '1') {
                    count++;
                    grid[i][j] = '0';
                    int index = i * column + j;
                    if (i>=1 && grid[i-1][j] == '1') {
                        merge(index, (i-1)*column + j);
                    }
                    if (i<grid.length-1 && grid[i+1][j] == '1') {
                        merge(index, (i+1)*column + j);
                    }

                    if (j>=1 && grid[i][j-1] == '1') {
                        merge(index, i*column + j - 1);
                    }
                    if (j<grid[0].length-1 && grid[i][j+1] == '1') {
                        merge(index, i*column + j + 1);
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        //char[][] grid = {{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};
        char[][] grid = {{'1'},{'1'}};
        NumIslandsUnionFindSolution solution = new NumIslandsUnionFindSolution();
        int res = solution.numIslands(grid);
        System.out.println(res);
    }
}
